#ifndef FORD_FALKERSON_H
#define FORD_FALKERSON_H

using namespace std;

//cписок ребер будет неудобен
class fordFalkerson{
public:
    //по входному графу формируем остаточный
    fordFalkerson(vector< vector<int> >& graph){
        residualGraph.resize(graph.size());
        for (int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph.size(); j++){
                residualGraph[i].push_back(make_pair(0,graph[i][j]));
            }
        }
    }

    int doFordFalkerson(int start, int finish){
        int maxStream = 0;
        //пока можем, ищем произвольные пути от страрта к стоку в остаточном графе
        int s = findWay(start,finish);
        while(s > 0){
            maxStream += s;
            s = findWay(start,finish);
        }
        return maxStream;
    }

    string getCubes(int cubesNumber){
        string result = "";
        for (int i = cubesNumber + 1; i < residualGraph.size() - 1; i++)
            {
                for (int j = 1; j <= cubesNumber; ++j)
                {
                    if (residualGraph[j][i].first > 0)
                    {
                        result.push_back(j + '0');
                        result.push_back(' ');
                    }
                }
            }
        return result;
    }

private:
    vector< vector <pair<int,int> > > residualGraph;
    int findWay(int start, int finish){
        int maxStream = INT_MAX;
        vector<bool> isVisited (residualGraph.size(),false);
        //по второму элементу пары будем понимать прямое ребро или обратное
        vector< pair<int,int> > parent (residualGraph.size());
        deque <int> queue;
        int j = start;
        isVisited[j] = true;
        parent[j] = make_pair(j,true);
        queue.push_back(j);
        //обходом в ширину пытаемся найти новый путь по прямым или обратным ребрам
        while(!queue.empty()){
            j = queue.front();
            queue.pop_front();
            for (int i = 0; i < residualGraph.size(); i++){
                bool valid = false;
                if ((! isVisited[i])
                        && (residualGraph[j][i].second - residualGraph[j][i].first > 0)){
                    valid = true;
                    queue.push_back(i);
                    isVisited[i] = true;
                    parent[i] = make_pair(j,true);
                    maxStream = min(maxStream, residualGraph[j][i].second - residualGraph[j][i].first);
                }
                if ((! isVisited[i])
                        && (residualGraph[i][j].first > 0)){
                    valid = true;
                    queue.push_back(i);
                    isVisited[i] = true;
                    parent[i] = make_pair(j,false);
                    maxStream = min(maxStream,residualGraph[i][j].first);
                }
                if (valid && i == finish){
                    int first = parent[i].first;
                    int second = i;

                    while (first != second){
                        if(parent[second].second){
                            residualGraph[first][second].first+=maxStream;
                        }else{
                            residualGraph[first][second].first-=maxStream;
                        }
                        second = first;
                        first = parent[second].first;
                    }
                    return maxStream;
                }
            }
        }
        return 0;
    }
};
#endif // FORD_FALKERSON_H
